package com.test.daily.leetcode.y2022.m06.day0614.v10;

/**
 * @author Tom on 2022/6/14
 */
public class Solution {

    public static int queen(int n){
        int[] record = new int[n];
        return process(0, n, record);
    }

    public static int process(int index, int N, int[] record){
        if(index == N){
            return 1;
        }
        int ans = 0;
        for(int j = index; j< N; j++){
            if(isValid(record, index, j)){
                record[index] = j;
                ans += process(index + 1, N, record);
            }
        }
        return ans;
    }

    public static boolean isValid(int[] record, int i, int j){
        for(int k = 0; k < i; k++){
            if(j == record[k] || Math.abs(k - i) == Math.abs(record[k] - j)){
                return false;
            }
        }
        return true;
    }
    public static int queen2(int n){
        if(n < 1 || n > 32){
            return 0;
        }

        int limit = 1 <<(n - 1) ;
        return process2(limit, 0, 0, 0);
    }
    public static int process2(int limit, int col, int left, int right){
        if(limit == col){
            return 1;
        }
        int cur = limit &(~(col | left | right));
        int pos = cur;
        int ans = 0;
        while(pos != 0){
            int rightestOne = pos &(~pos + 1);
            ans += process2(limit, col, (col | rightestOne) <<1, (col| rightestOne) >> 1);
            pos -= rightestOne;
        }
        return ans;
    }
}
